package com.qch.leecode.cyc2018.algorithm.a2_sort;

import com.qch.leecode.cyc2018.util_comom.Common;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 值得看等级：p1
 * 算法思想：排序(快速排序)：215.数组中的第K个最大元素
 * https://leetcode.cn/problems/kth-largest-element-in-an-array/
 * @Author qch
 * @Date 2022/11/15
 *
 * 自己解题：解不出，因为快速排序不会
 *
 * 解题思想：
 * 快速排序，由冒泡排序演变而来，使用分治法，交换排序
 * 快速排序思想：1.小于基准放左边，大于基准放右边 2.双指针
 * 1.选择基准元素pos->可随机，本题选择第一个（基准位置会在第一次计算后得出，成为左右边界的计算）
 *   设置最左和最右两个指针，重要：设置右指针位置是否为空的flag标记，在变成空，和填入值的时候变化状态
 * 先从最右（最左为基准，拿出来，所以最左为空，因此比右）开始比：
 *                      当右指针元素>=pos,不动，左指针位置仍为坑，右指针左移
 *                      当右指针元素<pos,右指针元素放到基左指针位置，右指针位置为新坑（flag标记修改），左指针右移
 *右指针所在位置为空时，再从最左开始比：
 *                       当左指针元素>=pos,左指针元素放到基右指针位置，左指针位置为新坑（flag标记修改），右指针左移
 *                       当左指针元素<pos,不动，右指针位置仍为坑，左指针右移
 *
 * 2.排到什么时候位置：
 * 本题注意：O(n)快速选择：分治法，到不可再分为止*
 *
 * 题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 *
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 *
*/
public class L1_KthLarges215 {
    public static void main(String[] args) {
//        int[] numbers={13,2,2,5,6,4};
//        int target=2;
       // int kthLargest = sort_findKthLargest(numbers, target);
//        int kthLargest = heap_findKthLargest(numbers, target);
//        System.out.println(kthLargest);

//        int i = part_quick(numbers,0);
//        Common.toString(numbers);
        int[] numbers={2,1};
        int target=2;
        int kthLargest = good_error_change_own_quick_findKthLargest(numbers,2);
        Common.toString(numbers);
        System.out.println(kthLargest);

    }

    /**
     * 使用排序:时间复杂度 O(NlogN)，空间复杂度O(1)
     * @param nums
     * @param k
     * @return
     */
    public static int sort_findKthLargest(int[] nums, int k) {
        //底层实现原理
        /**
         * 数组长度小于int QUICKSORT_THRESHOLD = 286
         * 286这个阈值时，且大于int INSERTION_SORT_THRESHOLD = 47
         * 47是，采用的就是快速排序了，小于47就采用插入排序
         *长度大于286后，就会采用归并排序了
         * 在采用归并排序之前，底层还是会遍历整个数组，为接下来的排序做好准备
         */
        Arrays.sort(nums);
        return nums[nums.length-k];
    }

    /**
     * 使用堆:时间复杂度O(NlogK)，空间复杂度O(K)
     * @param nums
     * @param k
     * @return
     */
    public static int heap_findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
//            if(queue.size()==0||queue.peek()<nums[i])
//            {queue.add(nums[i]);}
            queue.add(nums[i]);
            if(queue.size()>k)
            {
                //将队列中的首个元素弹出
                queue.poll();
            }
        }
        //peek：查看首个元素，不会移除首个元素，如果队列是空的就返回null
        return queue.peek();
    }

    /**
     * 快速选择：基于快速排序实现
     * 选择k大或者k小，只要一直排基准元素的一边
     *
     * 先从最右开始比，当最右>=pos,不动，左指针位置仍为坑，右指针左移
     *  *                   当最右<pos,最右放到基准元素位置，右指针位置为新坑，左指针右移
     *
     * 7 / 39
     * 用例：[2,1] 2
     *问题出在：
     * 1.一开始就不符合这个条件 k!=nums.length-lagerbegin
     * 2.数全在基准数左边，也不符合情况
     *
     */
    public static int error_own_quick_findKthLargest(int[] nums, int k) {
        int lagerbegin=0;
        int pos=0;
        int end=nums.length-1;
        while (k!=nums.length-lagerbegin)
        {
            lagerbegin= partition_part_quick(nums,pos,end);
            pos=lagerbegin+1;
        }
        return nums[lagerbegin];
    }

    /**
     * 针对上述错误进行修改
     * 递归思想
     * @param nums
     * @param k
     * @return
     */
    public static int good_error_change_own_quick_findKthLargest(int[] nums, int k) {
        callback_part_quick(nums,0,nums.length-1);
        return nums[nums.length-k];
    }
    public static void callback_part_quick(int[] partNum,int pos,int end)
    {
        if(pos>=end)
            return;
        int partition = partition_part_quick(partNum, pos, end);
        //后半段
        callback_part_quick(partNum,partition+1,end);
        //前半段
        callback_part_quick(partNum,pos,partition-1);
    }

    /**
     * 双边循环
     * @param partNum
     * @param pos
     * @param end
     * @return
     */
    public static int  partition_part_quick(int[] partNum,int pos,int end)
    {
        //默认基准元素为最左
        int posValue=partNum[pos];
        int left=pos;
        int right=end;
        boolean rightNull=false;
        while (left<partNum.length-1&&left!=right) {
            /**
             * 左右指针交替：
             * 1.left指针所在位置为空，比较right和基准
             * 1.right指针所在位置为空，比较right和基准
             * **
             */
            if(rightNull==false) {
                //比较右指针
                if (partNum[right] < posValue) {
                    partNum[left++] = partNum[right];
                    rightNull=true;
                } else {
                    right--;
                }
            }else {
                //比较右指针
                if (partNum[left] >= posValue) {
                    partNum[right--] = partNum[left];
                    rightNull=false;
                } else {
                    left++;
                }
            }
        }
        partNum[left]=posValue;
        return left;
    }
}
